#include<iostream>
#include<cstring>
using namespace std;
const int N = 5e4 + 10, INF = 1e9;
int g[N], h[N], f[N];
int w[N];
int n;
int main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> w[i];
		}
		h[0] = -INF;
		int s = -INF;
		for (int i = 1; i <= n; i++) {
			//f[i] = max(f[i - 1], 0) + w[i];
			s = max(s, 0) + w[i];
			h[i] = max(s, h[i - 1]);

		}
		g[n + 1] = -INF;
		s = -INF;
		for (int i = n; i; i--) {
			//f[i] = max(f[i + 1], 0) + w[i];
			s = max(s, 0) + w[i];
			g[i] = max(s, g[i + 1]);
		}

		int ans = -INF;
		for (int i = 1; i <= n; i++) {
			ans = max(ans, h[i] + g[i + 1]);
		}
		cout << ans << endl;
	}
	return 0;
}